By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 22, Issue 6, pp. 1117-1349

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Minimal NFA Problems are Hard

Tao Jiang and B. Ravikumar

pp. 1117-1141

BibTeX  Abstract Full Text:  PDF

An $O(m\log n)$-Time Algorithm for the Maximal Planar Subgraph Problem

Jiazhen Cai, Xiaofeng Han, and Robert E. Tarjan

pp. 1142-1162

BibTeX  Abstract Full Text:  PDF

On the Existence of Pseudorandom Generators

Oded Goldreich, Hugo Krawczyk, and Michael Luby

pp. 1163-1175

BibTeX  Abstract Full Text:  PDF

A Generalized Suffix Tree and Its (Un)Expected Asymptotic Behaviors

Wojciech Szpankowski

pp. 1176-1198

BibTeX  Abstract Full Text:  PDF

Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths

David R. Karger, Daphne Koller, and Steven J. Phillips

pp. 1199-1217

BibTeX  Abstract Full Text:  PDF

On Finding the Rectangular Duals of Planar Triangular Graphs

Xin He

pp. 1218-1226

BibTeX  Abstract Full Text:  PDF

Fast and Efficient Parallel Solution of Sparse Linear Systems

Victor Pan and John Reif

pp. 1227-1250

BibTeX  Abstract Full Text:  PDF

On-Line Bin Packing of Items of Random Sizes, II

WanSoo T. Rhee and Michel Talagrand

pp. 1251-1256

BibTeX  Abstract Full Text:  PDF

On the Computational Complexity of Small Descriptions

Ricard Gavaldà and Osamu Watanabe

pp. 1257-1275

BibTeX  Abstract Full Text:  PDF

VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions

Marek Karpinski and Thorsten Werther

pp. 1276-1285

BibTeX  Abstract Full Text:  PDF

Computing a Face in an Arrangement of Line Segments and Related Problems

Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, and Jack Snoeyink

pp. 1286-1302

BibTeX  Abstract Full Text:  PDF

A Better Heuristic for Preemptive Parallel Machine Scheduling with Batch Setup Times

Bo Chen

pp. 1303-1318

BibTeX  Abstract Full Text:  PDF

A New Method for Computing Page-Fault Rates

Jiang-Hsing Chu and Gary D. Knott

pp. 1319-1330

BibTeX  Abstract Full Text:  PDF

Learning Decision Trees Using the Fourier Spectrum

Eyal Kushilevitz and Yishay Mansour

pp. 1331-1348

BibTeX  Abstract Full Text:  PDF

Correction: Parallel Merge Sort

Richard Cole

p. 1349

BibTeX  Abstract Full Text:  PDF